//import java.util.HashMap;
//import java.util.Arrays;
//import java.util.Map;
class Solution {
    public int minCut(String s) {
        int n=s.length();
        int INF=0x3f3f3f;
        boolean[][] dict=new boolean[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j))
                    dict[i][j]=(i+1<j)?dict[i+1][j-1]:true;
            }
        }
        int[] dp=new int[n];
        Arrays.fill(dp,INF);
        dp[0]=0;
        for(int i=1;i<n;i++){
            if(dict[0][i]==true)
                dp[i]=0;
            else
            {
                for(int j=1;j<=i;j++){
                    if(dict[j][i]==true)
                        dp[i]=Math.min(dp[i],dp[j-1]+1);
                }
            }
        }
        return dp[n-1];
    }
}